1. Field of the Invention
The present invention generally relates to a multiprocessing computer system that uses superscalar microprocessors in a networked environment for message passing. More particularly, the invention relates to a distributed shared memory multiprocessing computer system that incorporates message passing priority rules to reduce network message routing latency.
2. Background of the Invention
Distributed computer systems typically comprise multiple computers connected to each other by a communications network. In some distributed computer systems, networked computers can access shared data. Such systems are sometimes known as parallel computers. If a large number of computers are networked, the distributed system is considered to be “massively” parallel. One advantage of a massively parallel computer is that it can solve complex computational problems in a reasonable amount of time.
In such systems, the memories of the computers are collectively known as a Distributed Shared Memory (“DSM”). It is a problem to ensure that the data stored in the DSM is accessed in a coherent manner. Coherency, in part, means that only one microprocessor can modify any part of the data at any one time, otherwise the state of the system would be nondeterministic.
Recently, DSM systems have been built as a cluster of Symmetric Multiprocessors (“SMP”). In SMP systems, shared memory can be implemented efficiently in hardware since the microprocessors are symmetric (e.g., identical in construction, in operation) and operate on a single, shared microprocessor bus. Symmetric Multiprocessor systems have good price/performance ratios with four or eight microprocessors. However, because of the specially designed bus that makes message passing between the microprocessors a bottleneck, it is difficult to scale the size of an SMP system beyond twelve or sixteen microprocessors.
It is desired to construct large scale DSM systems using microprocessors connected by a network. The goal is to allow microprocessors to efficiently share the memories so that data fetched by one program executed on a first microprocessor from memory attached to a second microprocessor is immediately available to all microprocessors.
DSM systems function by using message passing to maintain the coherency of the shared memory distributed throughout the multiprocessing computer system. A message is composed of packets that contain identification information and data. Control of message routing is distributed throughout the system so that each message traveling through the multiprocessing computer system is locally controlled by the particular microprocessor visited. Message passing can reduce system performance since delays in transmission of message packets can slow down program execution. Delays in transmission can occur because of high latency due to congestion in the network (i.e., many messages trying to go through the limited physical connections of the networks). This type of congestion can cause tremendous performance degradation that can result in high overall program execution times.
Prior art methods and systems to solve the problem of high network message routing latency typically involve implementing complex hardware solutions resulting in small performance improvements. These systems have resulted in message routing algorithms requiring a great amount of hardware, increasing cost without corresponding performance improvements to justify the cost. Prior art hardware solutions cause network oscillations in the DSM system since new packets injected into the network slow down old and long haul packets. Long haul packets are message packets that take more than a couple of hops to reach their destination, a hop being the passing of a message between two microprocessors. This builds up congestion in different parts of the network. As congestion clears up, various microprocessors in prior art DSM systems inject more packets into the network. This causes the congestion to build up again, thereby creating oscillatory behavior in the DSM system. Therefore, a new system and method to reduce network message routing latency and resulting network oscillations is needed that results in higher performance but reduced hardware costs and complexity.